package leetcode;

/**
 * @author yinlei
 * @date 2018/6/26
 * @since 1.0.0
 */
public class N029DivideTwoIntegers {

    public static void main(String[] args) {

//        System.out.println(Integer.MIN_VALUE);
//        System.out.println(Integer.MIN_VALUE - 1);
//        System.out.println(Integer.MIN_VALUE * -1);
//        System.out.println(Integer.toBinaryString(8));
//        System.out.println(Integer.MAX_VALUE / Integer.MIN_VALUE);
//
//        System.out.println(123);
//        System.out.println(123 * -1);
//
//        System.out.println(new N029DivideTwoIntegers().divide(Integer.MIN_VALUE, -2));

        toBit(8);

        System.out.println();
        System.out.println(divide(Integer.MIN_VALUE, Integer.MAX_VALUE));
        System.out.println(divide(8,5));
    }

    static public int divide(int dividend, int divisor) {

        boolean minVal = false;
        boolean minus = false;

        if (dividend < 0 || divisor < 0) {
            if (dividend < 0 && divisor < 0) {
                dividend = -dividend;
                divisor = -divisor;
            } else {
                dividend = dividend < 0 ? -dividend : dividend;
                divisor = divisor < 0 ? -divisor : divisor;
                minus = true;
            }

            if (dividend == Integer.MIN_VALUE) {
                minVal = true;
                dividend = dividend - 1;
            }
            if (divisor == Integer.MIN_VALUE) {
                return minVal ? 1 : 0;
            }
        }

        if (dividend < divisor) {
            return 0;
        }

        if (divisor == 1) {
            return minus ? (minVal ? Integer.MIN_VALUE : -dividend) : dividend;
        }

        int[] bit = toBit(dividend);
        int index = bit.length;
        int res = 0;
        int count = 0;

        while (index > 0) {
            int v = bit[index - 1];
            int data = (res << 1) + v;

            count = count << 1;
            if (data < divisor) {
                res = data;
            } else {
                count += 1;
                res = data - divisor;
            }
            index--;
        }

        // 如果最小值，在转换符号时，丢失1
        if (minVal && (res + 1) > divisor) {
            count++;
        }

        return minus ? -count : count;
    }

    static int[] toBit(int num) {
        int i = 0;
        int[] ii = new int[32];

        while (num > 0) {
            int d = 1 << i;
            ii[31 - i] = num & d >> i;

            num = num >> 1;
            i++;
        }

        int[] xx = new int[i];
        for (int j = 0; j < i; j++) {
            xx[j] = ii[31-j];
        }

        return xx;
    }

}
